package HashTable;//给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
//
// 示例 1: 
//
// 
//输入:
//"tree"
//
//输出:
//"eert"
//
//解释:
//'e'出现两次，'r'和't'都只出现一次。
//因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
// 
//
// 示例 2: 
//
// 
//输入:
//"cccaaa"
//
//输出:
//"cccaaa"
//
//解释:
//'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
//注意"cacaca"是不正确的，因为相同的字母必须放在一起。
// 
//
// 示例 3: 
//
// 
//输入:
//"Aabb"
//
//输出:
//"bbAa"
//
//解释:
//此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
//注意'A'和'a'被认为是两种不同的字符。
// 
// Related Topics 哈希表 字符串 桶排序 计数 排序 堆（优先队列） 👍 347 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
class frequencySort {
    public String frequencySort1(String s) {
        /**
         * 先利用哈希表 统计每个字符的频率
         * 对map根据value排序  利用list
         * */
        int len = s.length();
        if(len==0){
            return s;
        }
        //统计频率
        HashMap<Character,Integer> map = new HashMap<>();
        for (char ch: s.toCharArray()
        ) {
            map.put(ch, map.getOrDefault(ch,0)+1);
        }
        //借助list实现hashMap排序//
        //注意 ArrayList<>() 括号里要传入map.entrySet()
        ArrayList<Map.Entry<Character, Integer>> arrayList = new ArrayList<>(map.entrySet());
        //重写排序规则，按照value值从大到小排序
        Collections.sort(arrayList, new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                //根据value值从大到小
                return o2.getValue() - o1.getValue() ;
            }
        });
        String res = "";
        //注意这里遍历的是list，也就是我们将map.Entry放进了list，排序后的集合
        for (Map.Entry s1 : arrayList)
        {
            for (int i = 0; i < (int)s1.getValue(); i++) {
                res += s1.getKey();
            }
        }
        return res;
    }

    public String frequencySort(String s) {
        /**
         * 利用堆对map进行排序
         * */
        int len = s.length();
        if(len==0){
            return s;
        }
        //统计频率
        HashMap<Character,Integer> map = new HashMap<>();
        for (char ch: s.toCharArray()
        ) {
            map.put(ch, map.getOrDefault(ch,0)+1);
        }
        //创建一个map.size()大小的堆，并利用添加的key在map中的值重写排序
        PriorityQueue<Character> characters = new PriorityQueue<>(map.keySet().size(), new Comparator<Character>(){
            @Override
            public int compare(Character i1,Character i2){
                return map.get(i2) - map.get(i1);
            }
        });
        //将map的key添加到堆中
        for (Character ch: map.keySet()
             ) {
            characters.offer(ch);
        }
        //构建结果
        String res = "";
        while(!characters.isEmpty()){
            Character curr = characters.poll();
            for (int i = 0; i < map.get(curr); i++) {
                res += curr;
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
